package HashTable;

import java.util.HashMap;
import java.util.Map;

public class _560_SubarraySumEqualsK {
    public int subarraySum_0(int[] nums, int k) {
        int len = nums.length;
        int[] counts = new int[len + 1];
        int one = 0, zero = 0;
        counts[0] = 0;
        int total = 0;
        for (int i = 0; i < len; i++) {
            counts[i + 1] += (counts[i] + nums[i]);
        }
        //slide window size
        for (int i = 1; i <= len; i++) {
            for (int j = i; j <= len; j++) {
                if (counts[j] - counts[j - i] == k) {
                    total++;
                }
            }
        }
        return total;
    }

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> maps = new HashMap<>();
        maps.put(0, 1);
        int count = 0;
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (maps.containsKey(total - k)) {
                count += maps.get(total - k);
            }
            maps.put(total, maps.getOrDefault(total, 0) + 1);
        }
        return count;
    }
}